week9 HW 戴偉璿

1.\text{1.}

(a)(a)

PQ=Pf1(n)f2(f1(n))f3(f2(f1(n)))P\rightarrow Q = P\rightarrow f_1(n)\rightarrow f_2(f_1(n))\rightarrow f_3(f_2(f_1(n)))

複雜度為O(f1(n),f2(n),f3(n))=O(max(f1(n),f2(n),f3(n)))O(f_1(n),f_2(n),f_3(n))=O(max(f_1(n),f_2(n),f_3(n)))


(b)(b)

3.\text{3.}

將輸入的nn個數值進行編號並使其由小到大排列,以1,4,2,8,5,71,4,2,8,5,7為例,可以編號為(0,1),(1,4),(2,2),(3,8),(4,5),(5,7)(0,1),(1,4),(2,2),(3,8),(4,5),(5,7)四點,將其轉換成二維點後,尋找最近點對之距離,如果是等於11的話便表示有數字重複,反之則否。

4.\text{4.}

開另一個陣列b[]b[],將其中的數值皆設為零。然後歷遍原輸入陣列a[]a[],對於第ii項,將baib_{a_i}設為11代表該數字已經被用過了。如此,若遇到一個數字aka_k,其數值在b[]b[]對應到的bakb_{a_k}不為零時,可以確定該數字重複。

本作法時間複雜度為O(n)O(n),額外空間需求O(n)O(n),並且不會更改到原輸入陣列。